package dp.子序列;

import java.util.Arrays;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName N最长回文子串5.java
 * @Description https://leetcode-cn.com/problems/longest-palindromic-substring/
 * @createTime 2021年12月16日 20:58:00
 */
public class N最长回文子串5 {
	public String longestPalindrome(String s) {
		int length=s.length();
		if (length<2){
			return s;
		}
		char[] array = s.toCharArray();
		//定义dp[i][j] 表示 位置i到位置j 之间的字符串是不是回文
		boolean[][] dp=new boolean[length][length];

		for (int i = 0; i < length; i++) {
			dp[i][i]=true;
		}

		int maxLength=1;
		int begin=0;
		/**
		 * 状态方程
		 *   遍历字符串，从头到尾
		 *   1. 如果i=j 则必定是回文
		 *   2. 如果i≠j
		 *   	2.1 如果i到j之间的字符串个数小于3，则一定是回文
		 *   	2.2 如果i到j之间字符串个数大于3，则dp[i][j]=dp[i+1][j-1]
		 */
		for (int j = 1; j < length; j++) {
			for (int i = 0; i < j; i++) {
				if (array[i]==array[j]) {
					dp[i][j]=true;
				}else {
					if (j-i<3){
						dp[i][j]=true;
					}else {
						dp[i][j]=dp[i+1][j-1];
					}
				}

				if (dp[i][j]&&j-i+1>maxLength){
					maxLength=j-i+1;
					begin=i;
				}
			}
		}


		return s.substring(begin,maxLength);
	}
}
